package leetcode100;

// TODO 动态规划 | 状态转移方程 [经典] 【-】 最大子数组和
// TODO https://leetcode.cn/problems/maximum-subarray/?favorite=2cktkvj

public class lc100_0053 {

    public int maxSubArray(int[] nums) {
        int n = nums.length;
        // dp[i]表示，前i个元素最大连续子数组和，包含nums[i]元素
        // 声明dp, 初始化dp[0], maxSum
        int[] dp = new int[n];
        dp[0] = nums[0];

        int maxSum = dp[0];
        for (int i = 1; i < n; i++) {
            // 理清楚，如何得到前i个元素的最大值，这个逻辑算是简单的了
            // dp[i-1]+nums[i] < num[i]: 说明 dp[i-1] 已经是负的了，只能开启下一段统计
            dp[i] = Math.max(dp[i-1]+nums[i], nums[i]);
            maxSum = Math.max(maxSum, dp[i]);
        }
        return maxSum;
    }

}